# 创建链表类
from day07.SingleNode import SingleNode


class SingleLinkList(object):
    # 初始化属性，用head属性，指向：链表的第一个节点
    def __init__(self, node):
        self.head = node

    # 判断链表是否为空
    def is_empty(self):
        """
        判断链表是否为空
        如果head属性是None，链表为空
        如果head属性不是None，链表不为空
        :return: True 链表为空，False 链表不为空
        """
        # 第一种写法：
        # if self.head == None:
        #     return True
        # else:
        #     return False
        # 第两种写法：
        #return True if self.head == None else False
        # 第三种写法：
        return self.head == None

    # 链表的长度
    def length(self):
        """
        获取链表的长度
        遍历链表所有的节点，统计节点的个数
        :return: 节点的数量就是链表的长度
        """
        # 定义一个变量，表示链表的长度（节点数量）
        count = 0
        # 定义变量，表示当前节点，从头节点开始，往下逐个获取
        cur = self.head
        # 当“当前”节点不为空（存在），则累加节点数量
        while cur is not None:
            # 走到这里，说明节点不为空，则节点的个数加1
            count += 1
            # 继续获取下一个节点，next就是下一个节点的内存地址
            cur = cur.next

        # 返回节点数量
        return count

    # 遍历链表
    def travel(self):
        """
        遍历链表 : 打印每个节点的数据域
        :return:
        """
        # 定义变量，表示当前节点，从头节点开始，往下逐个获取
        cur = self.head
        # 当“当前”节点不为空（存在），则累加节点数量
        while cur is not None:
            # 打印当前节点的数据域
            print(cur.item)
            # 继续获取下一个节点，next就是下一个节点的内存地址
            cur = cur.next

    # 链表的头部添加元素
    def add(self, item): # item此时为0；
        # 将传入的item封装成节点
        new_node = SingleNode(item)
        # 设置新节点的地址域指向之前的旧的头部节点
        new_node.next = self.head
        # 设置新节点为：新的头部节点
        self.head = new_node

    # 链表的尾部添加元素
    def append(self, item):
        # 将传入的item封装成节点
        new_node = SingleNode(item)
        # 判断链表是否为空
        if self.is_empty():
            # 如果为空，将新节点设置为头节点
            self.head = new_node
        else:
            # 如果不为空，遍历链表，找到最后一个节点
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            # 当退出循环时，cur指向了最后一个节点
            # 将最后一个节点的地址域指向新节点
            cur.next = new_node

    # 链表的指定位置添加元素
    def insert(self, pos, item):
        # 场景1：如果pos<=0， 直接在链表头部添加元素
        if pos <=0:
            self.add(item)
        # 场景2：如果pos > 链表的长度，则直接在链表尾部添加元素
        elif pos >= self.length():
            self.append(item)
        # 场景3：如果pos在链表的中间位置，则需要遍历链表，找到指定位置
        else:
            # 定义变量count，用来表示插入位置钱的那个元素的索引。
            count = 0
            # 定义变量cur，表示当前元素（节点），找到插入位置前的那个节点
            cur = self.head
            # 遍历链表，判断：只要count的值<pos-1，循环继续，否则，退出循环
            while count < pos-1:
                count += 1
                # 获取当前元素（节点）,赋给cur并赋给下一个元素（节点）
                cur = cur.next
            # 创建一个新的节点
            new_node = SingleNode(item)
            new_node.next = cur.next
            # 将插入位置前的那个节点的地址域，指向新节点
            cur.next = new_node

    # 删除某个元素
    def remove(self, item):
        """
        :param item: 删除某个元素
        :return:
        """
        # 定义变量，cur， 记录：当前的节点，默认为第一个节点
        cur = self.head
        # 定义一个变量pre，记录当前节点的前一个节点
        pre = None
        # 遍历所有节点
        while cur is not None:
            # 判断当前节点的元素是否等于 被删除的节点元素，即：当前节点的数值域是否等于item
            if cur.item == item:
                # 场景1：有可能要删除的是第一个节点：头节点
                if cur == self.head:
                    # 说明要删除的是第一个节点
                    # 头节点，直接指向下一个节点
                    self.head = cur.next
                    # 断开旧的头结点和后续节点的链接（重置这个变量，跳出循环）
                    cur = None
                else:
                    # 场景2：要删除的节点不是头结点
                    # 上一个节点的next属性，指向当前节点的next属性
                    pre.next = cur.next
                    # 断开旧节点和后续节点的链接（重置这个变量，跳出循环）
                    cur = None
                # 核心细节，删除节点后，要跳出循环
                break
            else:
                # 走到这里，说明cur不是需要被删除的节点，继续往后遍历
                pre = cur       # pre表示刚才判断过得节点
                cur = cur.next  # cur更新为它的下一个节点

    # 查找指定元素的位置
    def search(self, item):
        """
        查找指定元素的位置
        :param item: 要查找的元素
        :return: 如果能够找到元素，返回True，反之返回False
        """
        # 定义一个变量，记录当前节点
        cur = self.head
        # 循环获取每个节点while cur != None:
        while cur is not None:
            # 判断当前节点的元素域（数值域）是否是要查找的值
            if cur.item == item:
                # 如果相等，返回True
                return True # 跳出循环
            # 否则，将当前节点更新为下一个节点
            cur = cur.next # 不匹配，开始校验下一个节点

        # 循环结束，没有找到元素，返回False
        return False
